#define _CRT_SECURE_NO_WARNINGS 1
class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        vector<vector<int>> ret;
        sort(nums.begin(), nums.end());

        int m = 0, a = 0, left = 0, right = 0, n = nums.size();
        if (n < 4) {
            return ret;
        }

        for (m = 0; m < n - 1;) {

            for (a = m + 1; a < n - 1;) {
                left = a + 1;
                right = n - 1;
                long long tar = (long long)target - nums[m] - nums[a];
                while (left < right) {
                    int sum = nums[left] + nums[right];

                    if (sum > tar)
                        right--;
                    else if (sum < tar)
                        left++;

                    else {

                        ret.push_back(
                            { nums[m], nums[a], nums[left], nums[right] });

                        left++;
                        right--;

                        while (left < right && nums[left] == nums[left - 1])
                            left++;
                        while (right > left && nums[right] == nums[right + 1])
                            right--;
                    }
                }
                a++;
                while (a < n && nums[a] == nums[a - 1])
                    a++;
            }

            m++;
            while (m < n && nums[m] == nums[m - 1])
                m++;
        }
        return ret;
    }
};